In computer networking, if the network is bisected into two partitions, the bisection bandwidth of a

network topology Network topology is the arrangement of the elements ( links, nodes, etc.) of a communication network. Network topology can be used to define or describe the arrangement of various types of telecommunication networks, including command and contro ...

is the bandwidth available between the two partitions. Bisection should be done in such a way that the

bandwidth Bandwidth commonly refers to: * Bandwidth (signal processing) or ''analog bandwidth'', ''frequency bandwidth'', or ''radio bandwidth'', a measure of the width of a frequency range * Bandwidth (computing), the rate of data transfer, bit rate or thr ...

between two partitions is minimum. Bisection bandwidth gives the true bandwidth available in the entire system. Bisection bandwidth accounts for the bottleneck bandwidth of the entire network. Therefore bisection bandwidth represents bandwidth characteristics of the network better than any other metric.

Bisection bandwidth calculations

For a linear array with n nodes bisection bandwidth is one link bandwidth. For linear array only one link needs to be broken to bisect the network into two partitions. Bisected linear array

For

ring Ring may refer to: * Ring (jewellery), a round band, usually made of metal, worn as ornamental jewelry * To make a sound with a bell, and the sound made by a bell :(hence) to initiate a telephone connection Arts, entertainment and media Film and ...

topology with n nodes two links should be broken to bisect the network, so bisection bandwidth becomes bandwidth of two links. Bisected ring

For

tree In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...

topology with n nodes can be bisected at the root by breaking one link, so bisection bandwidth is one link bandwidth. Bisected tree

For

Mesh A mesh is a barrier made of connected strands of metal, fiber, or other flexible or ductile materials. A mesh is similar to a web or a net in that it has many attached or woven strands. Types * A plastic mesh may be extruded, oriented, ex ...

topology with n nodes,

\sqrt

links should be broken to bisect the network, so bisection bandwidth is bandwidth of

\sqrt

links.

For Hyper-cube topology with n nodes, n/2 links should be broken to bisect the network, so bisection bandwidth is bandwidth of n/2 links. Bisected hypercube

Significance of bisection bandwidth

Theoretical support for the importance of this measure of network performance was developed in the PhD research o
Clark Thomborson (formerly Clark Thompson)
Thomborson proved that important algorithms for sorting,

Fast Fourier transform A fast Fourier transform (FFT) is an algorithm that computes the discrete Fourier transform (DFT) of a sequence, or its inverse (IDFT). Fourier analysis converts a signal from its original domain (often time or space) to a representation in th ...

ation, and matrix-matrix multiplication become communication-limited—as opposed to CPU-limited or memory-limited—on computers with insufficient bisection width. F. Thomson Leighton's PhD research tightened Thomborson's loose bound on the bisection width of a computationally-important variant of the

De Bruijn graph In graph theory, an -dimensional De Bruijn graph of symbols is a directed graph representing overlaps between sequences of symbols. It has vertices, consisting of all possible sequences of the given symbols; the same symbol may appear multiple ...

known as the

shuffle-exchange network In graph theory, the shuffle-exchange network is an undirected cubic multigraph, whose vertices represent binary sequences of a given length and whose edges represent two operations on these sequence, circular shifts and flipping the lowest-order ...

. Based on Bill Dally's analysis of latency, average case throughput, and hot-spot throughput of m-ary n-cube networks for various m, It can be observed that low-dimensional networks, in comparison to high-dimensional networks (e.g., binary n-cubes) with the same bisection width (e.g., tori), have reduced latency and higher hot-spot throughput.

References

Information theory Network management {{Compu-network-stub